题目链接

PTA上的一道 Dijkstra 题目，对该算法不太熟悉，做了挺久，最后测试点5，7过不去，看大佬的题解，发现错误的不仅仅是两个测试点，整个思路都有问题。

错误分析

错误代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
using namespace std;

int g[510][510], dist[510], w[510], pre[510], q[510];
bool st[510];

int main() {
	int bike, n, index, m;
	scanf("%d%d%d%d", &bike, &n, &index, &m);

	memset(g, 0x3f, sizeof g);
	memset(dist, 0x3f, sizeof dist);
	memset(pre, -1, sizeof pre);
	dist[0] = 0;
	int x = bike / 2;

	for (int i = 1; i <= n; i++) {
		scanf("%d", &w[i]);
		w[i] -= x;
	}
	for (int i = 0; i < m; i++) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		if (g[a][b] > c) {
			g[a][b] = g[b][a] = c;
			if (a == 0) pre[b] = 0;
		}
	}
	for (int j = 0; j < n; j++) {
		int t = -1;
		for (int i = 0; i <= n; i++)
			if (!st[i] && (t == -1 || dist[t] > dist[i]))
				t = i;

		st[t] = true;

		for (int i = 0; i <= n; i++) {
			if (!st[i] && g[t][i] != 0x3f3f3f3f) {
				if (dist[i] > dist[t] + g[t][i]) {
					dist[i] = dist[t] + g[t][i];
					q[i] = q[t] + w[i];
					pre[i] = t;
				} else if (dist[i] == dist[t] + g[t][i]) {
					if (abs(q[t] + w[i]) < abs(w[i]))
						q[i] = q[t] + w[i], pre[i] = t;
				}
			}
		}
	}
	if (q[index] < 0) printf("%d ", -q[index]);
	else printf("0 ");

	vector<int> v;
	for (int i = index; pre[i] != -1; i = pre[i]) {
		v.push_back(i);
	}
	printf("0");
	for (int i = v.size() - 1; i >= 0; i--)
		printf("->%d", v[i]);

	if (q[index] > 0) printf(" %d", q[index]);
	else printf(" 0");
	return 0;
}

错误点：

  • 与1003 Emergency 不同，本题不满足最优子结构，不能只用 Dijkstra 来做，挺严重的一错误。

  • 只能沿着最短路径的方向收集多余自行车，分给后面的节点；后面节点多出来的不能填到前面去，只能计入回收总量。

    例如路径上自行车数为5->0->10，并不能把最后一个节点上挪5个给中间的，需要送出5个，并回收5个。

    所以总需求量不能用 bike / 2 * 节点数 - 现有数来计算。

    否则测试点5、7均无法通过。

大神解法

柳神代码：1018. Public Bike Management (30)-PAT甲级真题（Dijkstra + DFS）

传统 Dijkstra 算法使用额外一维数组pre[]记录前导节点，通过pre[]可以倒推找回路径。若存在多条路径，则把pre[]扩展成二维数组pre[][]即可，pre[i][j]表示节点i的第j个前导节点。

从目标节点出发，可以直接找出其下一个节点。这样便相当于有了一个从目标节点出发，回到源节点的单向图。

深度遍历目标节点，即可考察完所有最短路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int inf = 99999999;
int cmax, n, sp, m;
int minNeed = inf, minBack = inf;
int e[510][510], dis[510], weight[510];	// e存储边权，dis[i]存储0到i的最短距离，weight存储点权
bool visit[510];	// 判断该点是否走过
vector<int> pre[510], path, temppath;	// pre[i][j]表示节点i的第j个前导节点，path存储最终路径，temppath存储用于深搜的临时路径
void dfs(int v) {	// 通过深搜来获取符合题意的最短路径
    temppath.push_back(v);
    if(v == 0) {
        int need = 0, back = 0;
        for(int i = temppath.size() - 1; i >= 0; i--) {	// 对0->v的每个点的点权进行判断
            int id = temppath[i];
            if(weight[id] > 0) {	// 点权>0表示车子要带走
                back += weight[id];
            } else {
                if(back > (0 - weight[id])) {	// 前面的点携带的车辆够后序点的优化 
                    back += weight[id];
                } else {	// 需要从0点携带车辆的情况
                    need += ((0 - weight[id]) - back);
                    back = 0;
                }
            }
        }
        if(need < minNeed) {	// 更新结果
            minNeed = need;
            minBack = back;
            path = temppath;
        } else if(need == minNeed && back < minBack) {
            minBack = back;
            path = temppath;
        }
        temppath.pop_back();
        return ;
    }
    for(int i = 0; i < pre[v].size(); i++)	// 递归v点的所有前导节点
        dfs(pre[v][i]);
    temppath.pop_back();
}
int main() {
    fill(e[0], e[0] + 510 * 510, inf);
    fill(dis, dis + 510, inf);
    scanf("%d%d%d%d", &cmax, &n, &sp, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &weight[i]);
        weight[i] = weight[i] - cmax / 2;
    }
    for(int i = 0; i < m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        scanf("%d", &e[a][b]);
        e[b][a] = e[a][b];
    }
    dis[0] = 0;
    for(int i = 0; i <= n; i++) {	// Dijkstra算法
        int u = -1, minn = inf;
        for(int j = 0; j <= n; j++) {
            if(visit[j] == false && dis[j] < minn) {
                u = j;
                minn = dis[j];
            }
        }
        if(u == -1) break;
        visit[u] = true;
        for(int v = 0; v <= n; v++) {
            if(visit[v] == false && e[u][v] != inf) {
                if(dis[v] > dis[u] + e[u][v]) {
                    dis[v] = dis[u] + e[u][v];
                    pre[v].clear();	// 有了更优解，要把之前的路径清空
                    pre[v].push_back(u);
                }else if(dis[v] == dis[u] + e[u][v]) {
                    pre[v].push_back(u);
                }
            }
        }
    }
    dfs(sp);
    printf("%d 0", minNeed);
    for(int i = path.size() - 2; i >= 0; i--)	// path存储完整的路径，所以从倒数第二个点开始输出
        printf("->%d", path[i]);
    printf(" %d", minBack);
    return 0;
}